package algorithm.swordoff;

/**
 * 1~n整数中1出现的次数
 * 很是麻烦,考到就GG,这题性价比不高
 *
 * K神的做法实在是神了..
 * 思路: 计算n的每一个位(个,十,百,千...)上出现1的个数,然后累加
 * 定义: 要计算的当前位上的数字为ni (0<=ni<=9),位用i表示(i=0是个位,i=1是十位...),数字左侧的是高位M,数字右侧的是低位N
 * ni=0时 此位可以表示成 M(0)N, 可以出现1的次数为 0..0(0)0..0 ~ (M-1)(9)9..9, 去掉ni位就是0~(M-1)9..9 即 (M-1-0+1)*10^i = M*10^i
 * ni=1时 此位可以表示成 M(1)N, 可以出现1的次数为 0..0(1)0..0 ~ M(1)N, 去掉ni位就是0~MN 即 M*10^i+N+1
 * ni>1时 此位可以表示成 M(X)N, 可以出现1的次数为 0..0(X)0..0 ~ M(1)9..9, 去掉ni位就是0~M(99..9) 即 (M+1)*10^i
 *
 * 可以把这个问题想象成一个K位的密码锁(k=log(10,n)  向上取整),固定某一位为1然后转动其他位置,以此遍历所有位
 */

public class SQ43 {

    public int countDigitOne(int n) {
        int digit = 1, res = 0;
        int high = n / 10, cur = n % 10, low = 0;
        while(high != 0 || cur != 0) {
            if(cur == 0) res += high * digit;
            else if(cur == 1) res += high * digit + low + 1;
            else res += (high + 1) * digit;
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return res;

    }

}
